package year2024.month4;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

public class KnightDialer {

    @Test
    void test1() {
        Assertions.assertEquals(10, knightDialer(1));
    }

    @Test
    void test2() {
        Assertions.assertEquals(20, knightDialer(2));
    }

    @Test
    void test3() {
        Assertions.assertEquals(136006598, knightDialer(3131));
    }

    /**
     * 935 骑士拨号器
     * 象棋骑士有一个独特的移动方式，它可以垂直移动两个方格，水平移动一个方格，或者水平移动两个方格，垂直移动一个方格(两者都形成一个 L 的形状)。
     * <p>
     * 象棋骑士可能的移动方式如下图所示:
     * <p>
     * <p>
     * 我们有一个象棋骑士和一个电话垫，如下所示，骑士只能站在一个数字单元格上(即蓝色单元格)。
     * <p>
     * <p>
     * 给定一个整数 n，返回我们可以拨多少个长度为 n 的不同电话号码。
     * <p>
     * 你可以将骑士放置在任何数字单元格上，然后你应该执行 n - 1 次移动来获得长度为 n 的号码。所有的跳跃应该是有效的骑士跳跃。
     * <p>
     * 因为答案可能很大，所以输出答案模 109 + 7.
     *
     * @param n
     * @return
     */
    public long knightDialer(int n) {

        long[][][] counts = new long[n + 1][3][4];
        for (int i = 0; i < counts.length; i++) {
            long[][] xCount = counts[i];
            for (int depth = 0; depth < xCount.length; depth++) {
                xCount[depth] = new long[]{-1, -1, -1, -1};
            }

        }

        long sum = 0;
        for (int x = 0; x < 3; x++) {
            for (int y = 0; y < 3; y++) {
                sum += find(x, y, n - 1, counts) ;
            }
        }

        return  find(1, 3, n - 1, counts) ;
    }

    long find(int x, int y, int n, long[][][] counts) {


        if (!(x == 1 && y == 3) && (x < 0 || x > 2 || y < 0 || y > 2)) {
            return 0;
        }

        if (counts[n][x][y] != -1) {
            System.out.printf("缓存命中 n = %d  x = %d y = %d 缓存 = %d\n", n, x, y, counts[n][x][y]);
            return counts[n][x][y];
        }

        if (n == 0) {
            return 1;
        }
        //   int max = 0;
        long temp = 0;
        temp += find(x + 1, y + 2, n - 1, counts);
        //  max = Math.max(max, temp);
        temp += find(x + 1, y - 2, n - 1, counts);
        //  max = Math.max(max, temp);
        temp += find(x + 2, y + 1, n - 1, counts);
        // max = Math.max(max, temp);
        temp += find(x + 2, y - 1, n - 1, counts);
        // max = Math.max(max, temp);

        temp += find(x - 1, y + 2, n - 1, counts);
        //  max = Math.max(max, temp);
        temp += find(x - 1, y - 2, n - 1, counts);
        //  max = Math.max(max, temp);
        temp += find(x - 2, y + 1, n - 1, counts);
        //  max = Math.max(max, temp);
        temp += find(x - 2, y - 1, n - 1, counts);
        // max = Math.max(max, temp);

        /*if (temp == 0) {
            return 0;
        }*/
        return counts[n][x][y] = temp > 1000000007?temp % 1000000007:temp;
    }
}
